package com.exercises;

import com.exercises.common.ListNode;

import java.lang.reflect.Array;
import java.nio.charset.Charset;
import java.util.*;

public class Exercise19 {

    public static void main(String[] args) {
        ListNode a = new ListNode(1);
        a.next(4).next(5);
        ListNode b = new ListNode(1);
        b.next(3).next(4);
        ListNode c = new ListNode(2);
        c.next(6);

        ListNode listNode = new Exercise19().mergeKLists(new ListNode[]{a, b, c});
        while (listNode != null) {
            System.out.println(listNode.val);
            listNode = listNode.next;
        }

    }

    public ListNode mergeKLists(ListNode[] lists) {
        TreeMap<Integer, ListNode> map = new TreeMap<>();
        for (ListNode l : lists) {
            while (l != null) {
                ListNode n = map.get(l.val);
                ListNode next = l.next;
                l.next = n;
                map.put(l.val, l);
                l = next;
            }
        }
        ListNode result = null, node = null;
        for (Map.Entry<Integer, ListNode> entry : map.entrySet()) {

            ListNode value = entry.getValue();
            while (value != null) {
                if (node == null) {
                    result = node = value;
                } else {
                    node.next = value;
                    node = node.next;
                }
                value = value.next;
            }

        }
        return result;
    }


}
